<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>The Effect of a Poor Initial Guess</title>
<link rel="stylesheet" href="../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../root_finding.html" title="Chapter 10. Root Finding &amp; Minimization Algorithms">
<link rel="prev" href="root_finding_examples/elliptic_eg.html" title="A More complex example - Inverting the Elliptic Integrals">
<link rel="next" href="bad_roots.html" title="Examples Where Root Finding Goes Wrong">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="root_finding_examples/elliptic_eg.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="bad_roots.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.bad_guess"></a><a class="link" href="bad_guess.html" title="The Effect of a Poor Initial Guess">The Effect of a Poor Initial Guess</a>
</h2></div></div></div>
<p>
      It's instructive to take our "toy" example algorithms, and use deliberately
      bad initial guesses to see how the various root finding algorithms fair. We'll
      start with the cubed root, and using the cube root of 500 as the test case:
    </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
              <p>
                Initial Guess=
              </p>
            </th>
<th>
              <p>
                -500% (≈1.323)
              </p>
            </th>
<th>
              <p>
                -100% (≈3.97)
              </p>
            </th>
<th>
              <p>
                -50% (≈3.96)
              </p>
            </th>
<th>
              <p>
                -20% (≈6.35)
              </p>
            </th>
<th>
              <p>
                -10% (≈7.14)
              </p>
            </th>
<th>
              <p>
                -5% (≈7.54)
              </p>
            </th>
<th>
              <p>
                5% (≈8.33)
              </p>
            </th>
<th>
              <p>
                10% (≈8.73)
              </p>
            </th>
<th>
              <p>
                20% (≈9.52)
              </p>
            </th>
<th>
              <p>
                50% (≈11.91)
              </p>
            </th>
<th>
              <p>
                100% (≈15.87)
              </p>
            </th>
<th>
              <p>
                500 (≈47.6)
              </p>
            </th>
</tr></thead>
<tbody>
<tr>
<td>
              <p>
                bracket_and_solve_root
              </p>
            </td>
<td>
              <p>
                12
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                10
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                13
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                newton_iterate
              </p>
            </td>
<td>
              <p>
                12
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                9
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                halley_iterate
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                schroder_iterate
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
</tr>
</tbody>
</table></div>
<p>
      As you can see <code class="computeroutput"><span class="identifier">bracket_and_solve_root</span></code>
      is relatively insensitive to starting location - as long as you don't start
      many orders of magnitude away from the root it will take roughly the same number
      of steps to bracket the root and solve it. On the other hand the derivative-based
      methods are slow to start, but once they have some digits correct they increase
      precision exceptionally fast: they are therefore quite sensitive to the initial
      starting location.
    </p>
<p>
      The next table shows the number of iterations required to find the second radius
      of an ellipse with first radius 50 and arc-length 500:
    </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
<col>
</colgroup>
<thead><tr>
<th>
              <p>
                Initial Guess=
              </p>
            </th>
<th>
              <p>
                -500% (≈20.6)
              </p>
            </th>
<th>
              <p>
                -100% (≈61.81)
              </p>
            </th>
<th>
              <p>
                -50% (≈61.81)
              </p>
            </th>
<th>
              <p>
                -20% (≈98.9)
              </p>
            </th>
<th>
              <p>
                -10% (≈111.3)
              </p>
            </th>
<th>
              <p>
                -5% (≈117.4)
              </p>
            </th>
<th>
              <p>
                5% (≈129.8)
              </p>
            </th>
<th>
              <p>
                10% (≈136)
              </p>
            </th>
<th>
              <p>
                20% (≈148.3)
              </p>
            </th>
<th>
              <p>
                50% (≈185.4)
              </p>
            </th>
<th>
              <p>
                100% (≈247.2)
              </p>
            </th>
<th>
              <p>
                500 (≈741.7)
              </p>
            </th>
</tr></thead>
<tbody>
<tr>
<td>
              <p>
                bracket_and_solve_root
              </p>
            </td>
<td>
              <p>
                11
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                5
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                7
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                9
              </p>
            </td>
<td>
              <p>
                8
              </p>
            </td>
<td>
              <p>
                6
              </p>
            </td>
<td>
              <p>
                10
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                newton_iterate
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                halley_iterate
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
</tr>
<tr>
<td>
              <p>
                schroder_iterate
              </p>
            </td>
<td>
              <p>
                4
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                2
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
<td>
              <p>
                3
              </p>
            </td>
</tr>
</tbody>
</table></div>
<p>
      Interestingly this function is much more resistant to a poor initial guess
      when using derivatives.
    </p>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
      Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
      Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
      Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
      Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="root_finding_examples/elliptic_eg.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="bad_roots.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
